Storing and retrieving data from a hard disk or other storage media is essential to modern electronics. For example, a host (e.g., a host computer) typically stores large amounts of data in an external memory. As such, it is important to quickly and accurately process data requests from the host to the external memory.
Conventionally, multiple queues are typically used to simultaneously process multiple data requests from a host to an external memory. Use of multiple queues permits parallel processing of multiple data requests (or commands) in different stages of the queues, and does not require each command to be completely processed before a next command is processed (as in a serial processing system).
Nevertheless, problems with queue overload can arise in a multiple-queue system. For example, a command from a host is typically immediately loaded into a first-stage queue, and the command may be quickly transferred to a next-stage queue if an external acknowledgment is not required. In contrast, deletion of a command from a last-stage queue (or end-stage queue) may take relatively more time, since an acknowledgement is typically required from the host. Thus, if commands are not deleted from the last-stage queue as quickly (or at least at the same rate) as commands are transferred from the first-stage queue, the last-stage queue will overflow, resulting in loss of commands and data.
In one conventional method to address such an overflow problem, each queue includes an additional register that stores a “data tag” for each command, in which the data tag indicates the present status of the command. Using mathematical equations that are based upon the present state of each command and the number of commands in each queue, the multiple-queue system determines whether to temporarily halt the input of data requests into the multiple-queue system.
However, this conventional method has several disadvantages. For example, implementing data tags requires that the multiple-queue system evaluate the status of every command in each queue. This can lead to substantial additional processing and/or reduced speed. Moreover, the mathematical equations for computing movement of commands are generally complex, and significant additional control logic must typically be added to the multiple-queue system, along with additional registers and buffer areas to store the data tags. Furthermore, the increased complexity makes such a multiple-queue system more difficult to debug.